package io.github.maojian.arr;

import org.junit.Test;

import java.util.LinkedList;
import java.util.List;

/**
 * 658. 找到 K 个最接近的元素
 * 给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
 */
public class Q658 {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int length = arr.length;
        List<Integer> ans = new LinkedList<>();
        //处理边界问题
        if (x < arr[0]) {
            for (int i = 0; i < k; i++) {
                ans.add(arr[i]);
            }
            return ans;
        }
        if (x > arr[length - 1]) {
            for (int i = k - 1; i >= 0; i--) {
                ans.add(arr[length - 1 - i]);
            }
            return ans;
        }
        //二分查找找出数组中最接近x的数组下标
        int left = 0, right = length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        right = left;
        left = right - 1;
        while (k-- > 0) {
            if (left < 0) {
                right++;
            } else if (right >= arr.length) {
                left--;
            } else if (x - arr[left] <= arr[right] - x) {
                left--;
            } else {
                right++;
            }
        }
        for (int i = left + 1; i < right; i++) {
            ans.add(arr[i]);
        }
        return ans;
    }


    @Test
    public void test() {
        int arr[] = new int[]{-2,-1,1,2,3,4,5};
        int k = 7, x = 3;
        findClosestElements(arr, k, x).stream().forEach(System.out::println);
    }
}
